The present invention relates to a CRC (Cyclic Redundancy Check) operating method for performing a CRC operation on an encoded word and to an HEC (Head Error Checker) synchronizing unit for detecting an error in a header of a cell and synchronizing a cell in an ATM switching method.
A typical method of detecting and correcting an error in data used in a data process or data communication, etc., is a cyclic redundancy check (hereinafter referred to as a CRC). This is a checking method based on the fact that an encoded polynomial containing a cyclic code (cyclic replacement of any encoded word results in another encoded word) can be divided by a generated polynomial.
For example, when data are encoded, they are segmented in predetermined length units. Next, a CRC code can be obtained as a polynomial code indicating a remainder of a division by dividing by mod (modulo) 2 and by an appropriately generated polynomial in the binary representation comprising predetermined length data to be processed. Then, the CRC code is applied to the original data to be processed. An encoded polynomial comprising an encoded word necessarily comprises a cyclic code divided by the above described generated polynomial.
When an encoded word formed by adding a CRC code is decoded, it is segmented in the same length units as in the encoding process. Then, a CRC operation is performed in which the encoded polynomial comprising encoded words of predetermined length is divided by the same generated polynomial as that used in the encoding process. If the remainder is "0", it means that no errors have arisen in the encoded word from the encoding process to the decoding process. However, a remainder other than "0" means an error has arisen.
An example of a circuit using a CRC operation is an HEC synchronizing circuit in an ATM switching method.
In an ATM (Asynchronous Transfer Mode) switching method, communication data are divided into fixed lengths of 53 bytes. Then, each cell is transmitted after being multiplexed to the time slots in the transmission line. A large-capacity, high-speed communication network can thus be realized by autonomously switching the cell with a hardware switch according to the destination information added at the header part of each cell.
FIG. 1 shows the general configuration of an ATM switching unit. Each cell is transmitted via a large capacity ATM transmission line (optical transmission line) 101 at a transmission speed of 600 Mbps (megabits/second), for example. Each transmission line 101 is terminated by a transmission line terminal unit 102, multiplexed by a multiplexer (MUX) 103 and then switched by an ATM switch 104.
In the transmission line 101, each cell is multiplexed as shown by (a) of FIG. 2 to a predetermined 53-byte time slot and transmitted in the direction indicated by the arrow shown by (a) of FIG. 2. Each cell comprises a header part containing its destination information, etc., and an information part containing communication information.
In a MUX 103 shown in FIG. 1, a multiplexed cell is re-multiplexed to a plurality of transmission lines after being inputted from each ATM transmission line 101. Therefore, the cell input timing through the ATM transmission line 101 must be exactly synchronized. The synchronizing operation is realized as an operation by a transmission line terminal unit 102 of detecting the head of a cell header applied through each of the ATM transmission lines 101.
FIG. 3 shows the general configuration of each of the transmission line terminal units 102 for realizing the above described synchronizing operation. An HEC (described later) synchronizing circuit 301 detects the input timing of the header part of a cell 304 inputted from the transmission line 101. A cell synchronization determining circuit 302 determines the stable input timing of a cell by detecting in the HEC synchronizing circuit 301 the repetition of the input timing of a header part of a plurality of cells 304. Then, the circuit 302 outputs a cell synchronizing pulse 305 as shown in FIG. 2. According to a cell synchronizing pulse 305, a cell 304 temporarily stored by a delay circuit 303 is outputted toward the MUX 103 shown in FIG. 1 according to the timing shown in (a) and (b) of FIG. 9. In the MUX 103 shown in FIG. 1, each of the cells 304 transmitted from each of the transmission line terminal units 102 is multiplexed according to the cell synchronizing pulse 305 provided by each of the transmission line terminal units 102.
A header part of a cell comprises 5-byte data, the last byte of which is called an HEC (Header Error Checker). The HEC is a CRC code added to 4-byte data transmitted as destination information on the sending side. That is, on the sending side, a one-byte CRC code can be obtained as a remainder of a division by dividing a polynomial in the binary representation comprising the above described 4-byte data to be transmitted by the generated polynomial x.sup.8 +x.sup.2 +x+1. The 5-byte data of a header part of a sending cell can be generated by adding the CRC code to the 4-byte data to be transmitted.
On the receiving side, in response to the generation of a sending header part, the HEC synchronizing circuit 301 (FIG. 3) sequentially retrieves 5-serial-byte data by moving each of their positions forward by one byte each. Then, a CRC operation is performed such that a binary polynomial comprising 5-byte-data to be received is divided by the generated polynomial used on the sending side. As indicated by the principle of the above described CRC operation, the remainder of the division in which a 5-byte coded-word polynomial is divided by a generated polynomial used on the sending side must be "0" if the 5-byte data of a header part are correctly extracted on the receiving side. The HEC synchronizing circuit 301 must detect as current input timing of an errorfree header part of a cell 304 (FIG. 3) the input timing of 5-byte data to be received when a remainder "0" is obtained in the above described CRC operation. That is, the HEC synchronizing circuit 301 detects the input timing of a header part and simultaneously detects errors therein.
FIG. 4 shows a configuration sample of the prior art technology of the HEC synchronizing circuit for realizing the detecting operation for a header part.
As described above, the HEC synchronizing circuit 301 must sequentially retrieve 5-serial-byte data by moving each of their positions forward by one byte each. Then, a CRC operation is performed such that a binary polynomial comprising 5-byte-data to be received is divided by the generated polynomial used on the sending side. In this case, the data is sequentially received in a byte unit, stored in a flip-flop (FF) 402.sub.0, sequentially shifted in a byte unit in FF402.sub.1 -FF402.sub.4, and 5-byte receiving data are retrieved as the output of FF402.sub.0 -402.sub.4. Each of the FFs stores data in a byte unit. Conventionally, five CRC operating circuits CRCCs 401.sub.1 -401.sub.5 for performing a byte-by-byte CRC operation are connected in serial. In each CRCC 401, a CRC operation is performed such that each byte in the 5-byte data is divided by a generated polynomial x.sup.8 +x.sup.2 +x+1. In this case, an operation result obtained by the operation in the previous CRCC 401 (the remainder after dividing each byte datum by a generated polynomial) is provided to the next CRCC 401. The all "0" data are applied as an initial value to the first CRCC 401.
FIG. 5 shows the circuit configurations of each of the CRCCs 401.sub.1 -401.sub.5 shown in FIG. 4. In FIG. 5, a.sub.0 -a.sub.7 are received data outputted from the FF 402, b.sub.0 -b.sub.7 are results of the CRC operation in the previous CRCC 401, and c.sub.0 -c.sub.7 are results of the CRC operation in the present CRCC 401. a.sub.7, b.sub.7, and c.sub.7 are MSBs, that is, the most significant bits, and a.sub.0, b.sub.0, and c.sub.0 are LSBs, that is, the least significant bits. The circuit configuration shown in FIG. 5 is well-known for performing a CRC operation and comprises a combination of exclusive logical sum (EOR) elements.
However, as indicated in FIG. 4, the conventional HEC synchronizing circuit requires five serially connected CRC operating circuits (CRCC) 401.sub.1 -401.sub.5, and the hardware is configured in a large scale. Specifically, in the ATM switching method, the hardware must be configured in the smallest possible scale because 1-byte data are processed at a very high clock speed of 18.75-75 MHz.
The above described problem is not limited to an HEC synchronizing circuit in an ATM switching method, but also occurs in a CRC operating unit for sequentially performing a CRC operation to detect the segmentation of data containing a CRC code and for detecting errors in the data.